/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * dfs
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (root === null) return 0
    return getDepth(root, 0)
};

function getDepth(root, depth) {
    if (root === null) return depth
    depth++
    return Math.max(getDepth(root.left,depth),getDepth(root.right,depth))
}


/**
 * 后来又做了一个类似的递归解法
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    return getMaxDepth(root)
}

const getMaxDepth = (root) => {
    if (root === null) return 0
    let leftDepth = getMaxDepth(root.left)
    let rightDepth = getMaxDepth(root.right)
    // 自底向上加1
    return Math.max(leftDepth, rightDepth) + 1
}


/**
 * bfs，广度优先
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (root === null) return 0
    let stack = [root],
        len,
        node,
        depth = 0;
    while (stack.length > 0) {
        len = stack.length;
        depth++;

        for (let i = 0; i < len; i++) {
            node = stack.shift()
            node.left && stack.push(node.left)
            node.right && stack.push(node.right)
        }
    }
    return depth;
}